1. Field of the Invention
This invention relates to graphics display systems, and in particular, to a system for specifying the color and intensity of pixels in an image to be displayed on such systems.
2. Description of the Prior Art
Three-dimensional computer graphics displays are used to display images to a user as if he were observing a real world environment. These systems store in a data base a representation in three-dimensional coordinates of three-dimensional objects, as well as information concerning their color and other properties. Additional "environment" information including the number, color, location, and other properties of illumination sources, atmospheric properties, and many other details also may be specified. The display is generated after being provided with the desired viewing angle for the viewer. In addition, the user may specify the field of view, the size of the image to be produced, and the back plane of the viewing volume so as to include or eliminate background as desired. The system must calculate all the details of the image, including determining which objects obscure others from the viewer's point of view, and present them accordingly.
The image data base in a typical graphics display system stores a description of each object in a scene as a number of small polygons which cover the surface of the object in the same manner that a number of small tiles can cover a wall or other surface. Each polygon is described by a list of its vertex coordinates (X, Y, Z) and a specification of material surface properties (e.g., color, texture, shininess, etc.), as well as possibly the normal vectors to the surface at each vertex. For three-dimensional objects with complex curved surfaces, the polygons in general are triangles or quadrilaterals (which can be decomposed into pairs of triangles).
In such systems a transformation engine transforms the object coordinates in response to the angle of viewing selected by a user. A clipping circuit eliminates the triangles which are outside the viewing area and "clips" the polygons which are partly inside and partly outside the viewing area. The vertices of the resulting polygons are transmitted by the clipping circuit to the next stage in coordinates corresponding to the viewing screen (X, Y coordinates) with an associated depth for each vertex (Z coordinate). In a typical prior art system, a lighting model 20 is applied next to specify the color of each triangle. Then the triangles with their color values are transmitted to a rasterizer.
For each polygon, the rasterizer determines which pixel positions are covered by that triangle and compares the depth values (Z) for the polygon being processed with the depth value of any pixel which already in the frame buffer. If the depth value of the new polygon pixel is smaller, indicating that it is in front of the polygon already written into the frame buffer, then the new value replaces the value in the frame buffer. This process is repeated until all polygons have been rasterized. Then the video controller displays the contents of the frame buffer on a display a scan line at a time in raster order.
A number of systems have been designed to improve upon the above basic system. With recent improvements in floating point processing and polygon fill algorithms, the main bottleneck of the basic system is the amount of time required to rasterize each polygon, compare each pixel generated to the one already stored in the frame buffer, and then write the pixel into the frame buffer. The time required to repeat this process for each pixel of each polygon is substantial.
The basic method is characterized by a single rasterization processor writing pixels one by one into a frame buffer. The improved systems are characterized by employing a large number of processors in parallel in which the individual processors represent pixels in the frame buffer. These systems differ in how the processors are assigned to pixels.
An approach known as the pixel-planes method employs brute force and assigns a processor for every pixel in the display screen. See, for example, Foulton, et al., Pixel Planes: Building a VLSI-Based Graphics System, 1985 Chapel Hill Conference on Very Large Scale Integration 35 (H. Fuchs ed., 1985). The edges are two-dimensional polygon descriptions are sent one by one to the pixel processors. The processors determine which side of each edge the pixel they represent is on, and consider themselves inside a particular polygon only if they are on the correct side of all its edges. Next, if the depth information is less than that of any previously stored pixel value, the pixel processors load interpolated depth and color information into their pixel value registers. When all polygons have been processed, the information stored for each pixel is supplied to the display in raster scan order. This system is faster then the basic system because the drawing time for any polygon is constant, regardless of the number of pixels effected by the polygon (the area of the polygon). The disadvantage is that an extremely large number of processors is needed. For instance, a 1000.times.1000 pixel display would require at least a million processors. This disadvantage is only somewhat mitigated by placing multiple pixel processors on a single chip.
Another system known as the Scan Line Access Memory (SLAM) requires custom storage registers for each pixel in the display, but only contains enough pixel processors for a single scan line. Such a system is described in Demetrescu, High Speed Image Rasterization Using Scan Line Access Memories, 1985 Chapel Hill Conference on Very Large Scale Integration 35 (H. Fuchs ed., 1985). External rasterization hardware breaks each polygon into horizontal runs of pixels. Only the start and stop addresses of these runs are entered into the SLAM chips, and the internal one-dimensional array of pixel processors determines which pixels are covered by this run. The results are written into an on-chip memory array, indexed by the y location of the particular run. When all polygons have been processed, internal double buffering allows the information stored at each pixel to be supplied to the display in raster scan order. This system allows large polygons to be rasterized in a time dependent primarily upon their height, not their area. Compared to pixel planes, the smaller number of pixel processors reduces the number of chips needed. Unfortunately, considerable external circuitry must break up polygons into pixel runs, and sequence this data to the SLAM chips. The line-by-line overhead required per polygon reduces the overall speed of the system. Finally, the requirement for on-chip RAM resources for all pixels effected by the local pixel processors requires an exorbitant number of chips for a functional 1000.times.1000 display.
Another system, the super buffer, also employs a single scan line of pixel processors, but does not require local memory for all the pixels effected by them to be on the same chip. This system is described in Gharachorloo and Pottle, Super Buffer: A Systolic VLSI Graphics Engine for Real Time Raster Image Generation, 1985Chapel Hill Conference on Very Large Scale Integration 35 (H. Fuchs ed., 1985). The previous two systems take input polygons one at a time, rasterizing each one completely before going on to the next. The super buffer requires all the polygons to be displayed to be presorted by the y scan line on which they first appear. Each polygon is broken into runs on a scan line basis and the runs sent to the pipe of pixel processors. All runs for all polygons for a given scan line must be sent before sending any runs for any further scan lines. This requires a buffer of partially rasterized polygons to be kept. This system has the advantage that the time to rasterize a given polygon is dependent only on the height of the polygon, and not its area. It also has the advantage that the number of chips required by the system is considerably fewer than in the other two systems. Unfortunately, however, it shares SLAM's requirement for an off-chip polygon run generator, and adds the requirement for juggling several active polygons at a time within this generator. A further requirement is an off-chip memory subsystem to store and sort by starting Y scan line all the polygons to be displayed.